package leetcode.code033;

public class Search extends Solution033 {

	@Override
	public int search(int[] nums, int target) {
		int len = nums.length;
		int res = -1;
		if (len == 1)
			return nums[0] == target ? 0 : -1;
		if (len == 2)
			return nums[0] == target ? 0 : nums[1] == target ? 1 : -1;
		int l = 0;
		int r = len - 1;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (nums[m] == target)
				return m;
			if (target > nums[m]) {
				if (nums[m] < nums[r]) {
					if (target < nums[r]) {
						l = m + 1;
					} else {
						r = m - 1;
					}
				} else {
					// m > r target m max target r
					l = m + 1;
				}
			} else {
				if (nums[m] < nums[r]) {
					r = m - 1;
				} else {
					if (target < nums[l]) {
						l = m + 1;
					} else {
						r = m - 1;
					}
				}

			}
		}
		return res;
	}

	public static void main(String[] args) {
		Search search = new Search();
		search.debug1();
		search.debug2();
		search.debug3();
		search.debug4();
		search.debug5();
	}

}
